This invention relates to data processing equipment and more particularly to circuits for allowing a multi-way program branch to any one of a preselected plurality of random memory locations in one instruction execution cycle, said selection based upon the contents of a data register. Appropriate use of this multi-way branching capability on any set of variables selected by the programmer minimizes the amount of memory and time required to implement and run computer programs.
In a typical machine language program, a conditional branch is implemented through the use of a conditional branch instruction followed by a location address. The conditional branch instruction will look at some hardware state, an overflow indicator for instance, and on the basis of that indicator either branch to the specified location or skip the next line of the program and continue on. This would be an example of a two-way branch in that the program either branches to the specified location or continues on with the program, the decision being based on a data bit.
Three-way branches are commonly seen in machine language programs as comparison instructions. A word in memory is typically used as a reference against which the contents of the accumulator are compared. Two addresses typically follow the instruction, the first address being the one that the program will branch to in case the reference is larger, and the second being the address the program will branch to in case the reference is smaller. If the two values are equal the program will continue on.
The problem with these two kinds of branch instructions is that they interrogate the data bit by bit. In the case where the data field is long and complex, it can be seen that these techniques would involve a multiplicity of shifting and testing instructions which would slow down the program and use a substantial amount of memory.
In some applications where high speed is necessary, and where memory capacity is ample, a table look-up method is used where the data itself becomes the least significant bits of the address field. Using an example of an eight bit data field in a system where a memory location has a 16 bit address, one may mask together the most significant eight bits of the address field and use the eight bits of data as the least significant eight bits of the address field. A branch to this address would immediately provide each separate data bit configuration with a distinct location to branch to. Each of these 256 locations could, in turn, contain an unconditional branch instruction to any location in memory. Thus, each combination of bits would force the program to a different and independent memory location. The problem with this system, of course, is that 256 words of memory must be used every time this branch technique is used.
A hardware variation of the table look-up method is employed in microprogrammable computers to branch to that part of the microprogram in the control memory required to implement the operation code being executed. For a numerical example, assume that the operation code is contained in the machine language program as an eight bit field and that all the programs needed to implement the entire operation code vocabulary are located in the first thousand words of microcode. In this case, an eight by ten bit matrix could be used to convert the eight bit operation code directly into a ten bit address. Appropriate hardware to allow for a direct branch to the address thus produced would have the desired result of branching directly to one of a plurality of preselected memory locations based on the contents of the operation code field. However, even where this specialized multi-way branching capability is provided for the processing of operation codes, in the remainder of the program, wherein numerous branches must be made on complex fields of data, the programmer is forced to rely on the process of shifting and testing bit by bit or on the table look-up method.